package com.ls.linkList;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;

import java.util.LinkedList;

/**
 * 带头节点单链表
 */
@Data
@Builder
@AllArgsConstructor
public class SingleList {
    private int data;
    private SingleList next;

    public static void main(String[] args) {
        SingleList singleList = new SingleList(1);
        singleList.addTail(new SingleList(2));
        singleList.addTail(new SingleList(3));
        singleList.addTail(new SingleList(4));
        // 头部添加元素

        singleList.show();
        System.out.println();
        SingleList reverseList = singleList.reverseList();
        reverseList.show();
//        System.out.println(singleList.getLast(2).data);
//        singleList.add(2,new SingleList(4));
//        singleList.show();
//        System.out.println();
//        singleList.delete(1);
//        singleList.show();
//        singleList.addFront(new SingleList(4)).show();
        // 长度
//        System.out.println(singleList.length());
//        singleList.show();
    }

    public SingleList(int data) {
        this.data = data;
    }

    /**
     * 尾部添加元素
     */
    public void addTail(SingleList singleList){
        // 遍历到链表尾部
        SingleList current = this;
        while (current.next!=null){
            current = current.getNext();
        }
        current.setNext(singleList);
    }
    /**
     * 头部添加元素
     */
    public SingleList addFront(SingleList singleList){
        return SingleList.builder().next(this).data(singleList.data).build();
    }
    /**
     * 遍历
     */
    public void show(){
        SingleList current = this;
        while (current.next!=null){
            System.out.print(current.data+"-->");
            current = current.getNext();
        }
        System.out.print(current.data+"-->null");
    }
    /**
     * 长度
     */
    public int length(){
        SingleList current = this;
        int length = 1;
        while (current.getNext()!=null){
            length++;
            current = current.getNext();
        }
        return length;
    }
    /**
     * 中间位置添加元素
     */
    public void add(int position,SingleList target){
        // 添加位置不合理
        if (position<1 || position > this.length()+1){
            throw new RuntimeException("添加位置不合理");
        }
        // 遍历到插入位置的前一个位置
        SingleList current = this;
        int index = 1;
        while (index<position-1){
            current = current.getNext();
            index++;
        }
        target.setNext(current.getNext());
        current.setNext(target);
    }
    /**
     * 删除元素
     */
    public void delete(int position){
        if (position<1 || position > this.length()){
            throw new RuntimeException("删除位置不合理");
        }
        // 删除的是第一个节点，由于没有设置头节点
        if (position==1){
            System.out.println("首节点暂无法删除");
            return;
        }
        // 遍历到删除位置的前一个节点，单向链表无法找到前一个节点
        SingleList current = this;
        int index = 1;
        while (index<position-1){
            current = current.getNext();
            index++;
        }
        current.setNext(current.getNext().getNext());
    }
    /**
     * 3.得到倒数第几个的位置
     * @param position
     */
    public SingleList getLast(int position){
        if (position<1 || position>this.length()){
            throw new RuntimeException("位置不合理");
        }
        SingleList current =  this;
        // 计算遍历的次数
        int count = length() - position;
        while (count>0){
            current = current.getNext();
            count--;
        }
        return current;
    }
    /**
     * 4.单链表反转
     * 思路：
     *  1.不断遍历链表，将curr指向下一节点
     *  2.保存前一个反转链表
     *  3.遍历到一个节点就设置它的下一个为上一个反转链表
     *  4.最终返回最后一个节点的地址就是反转链表了
     */
    public SingleList reverseList(){
       SingleList reverseList = null;
       SingleList next = null;
       SingleList curr = this;
       while (curr!=null){
           next = curr.getNext();
           curr.setNext(reverseList);
           reverseList = curr;
           curr = next;
       }
       return reverseList;
    }
}
